import java.util.ArrayList;

/**
 * Created by forcht on 2018/7/14.
 */
public class Solution {
    ArrayList<String> list=new ArrayList<>();
    public ArrayList<String> letterCombinations(String digits) {
       dfs(digits,0,new StringBuilder());
       return list;
    }

    public void dfs(String digits,int cur,StringBuilder builder){
        if (cur>=digits.length()) {
            list.add(builder.toString());
            return;
        }
        int n=digits.charAt(cur)-'0';
        int j=3;
        if (n==7||n==9) {
            j = 4;
        }
        if (n==8||n==9){
            n=(n-2)*3+97+1;
        }
        else n=(n-2)*3+97;
        for(int i=0;i<j;i++){
            builder.append((char)(n+i));
            dfs(digits,cur+1,builder);
            builder.deleteCharAt(builder.length()-1);
        }
    }

    public static void main(String[] args) {
       Solution solution=new Solution();
        System.out.println(solution.letterCombinations("789"));
    }
}
